package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/univalued-binary-tree/"/>单值二叉树(Univalued Binary Tree)</a>
 * <p>如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。</p>
 * <p>只有给定的树是单值二叉树时，才返回 true；否则返回 false。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：[1,1,1,1,1,null,1]
 *      输出：true
 *
 * 示例 2：
 *      输入：[2,2,2,5,2]
 *      输出：false
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>给定树的节点数范围是 [1, 100]。</li>
 *     <li>每个节点的值都是整数，范围为 [0, 99] 。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/17 16:59
 */
public class LC0965UnivaluedBinaryTree_S {

    static class Solution {
        public boolean isUnivalTree(TreeNode root) {
            return dfs(root, root.val);
        }

        private boolean dfs(TreeNode node, int targetVal) {
            if (node == null) {
                return true;
            }
            if (node.val != targetVal) {
                return false;
            }
            return dfs(node.left, targetVal) && dfs(node.right, targetVal);
        }

        public boolean isUnivalTree2(TreeNode root) {
            int val = root.val;
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode poll = queue.poll();
                if (poll.val != val) {
                    return false;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(1);
        root1.left.left = new TreeNode(1);
        root1.left.right = new TreeNode(1);
        root1.right.right = new TreeNode(1);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(1);
        root2.left.left = new TreeNode(3);
        root2.left.right = new TreeNode(1);
        root2.right.right = new TreeNode(1);

        Solution solution = new Solution();
        System.out.println(solution.isUnivalTree(root1));
        System.out.println(solution.isUnivalTree(root2));


    }
}
